package games.graphPath;

import games.graphPath.Graph.Edge;
import games.graphPath.Graph.Vertex;

import java.util.ArrayList;
import java.util.Collections;
import java.util.Random;

import commonDataStructures.BinaryHeap;

public class GraphPathGradientSearch{

	protected Graph _graph;

	protected int _maxDepth;

	public GraphPathGradientSearch(Graph g, int maxDepth)
	{
		_graph = g;
		_maxDepth = maxDepth;
	}

	public void search(GraphPathResult r,int iterations){
	
		long beginTime = System.currentTimeMillis();
		
		int depth = _graph.getVertexs().size();
		
		ArrayList<Edge> bestPath = null;
		int minCost = 0;
		
		Random rand = new Random();
		
		int src = _graph.getSrc().getIndex();
		int dst = _graph.getDst().getIndex();
		
		for (int i=0; i<iterations; i++)
		{
			ArrayList<Edge> curPath = new ArrayList<Edge>();
			int cost = 0;
			int count = 0;
			BinaryHeap<Edge> moves = new BinaryHeap<Edge>();
			Edge curEdge;
			Vertex v = _graph.getVertexs().get(rand.nextInt(_graph.getVertexs().size()));
		
			if (v.getIndex() != src && v.getInNeighbors().size()==0
					|| v.getIndex() != dst && v.getOutNeighbors().size()==0)
				continue;
				
			
			//search from 'v' to the source
			for (Edge edge : v.getInNeighbors())
			{
				moves.insert(edge);
			}
			
			boolean found = false;
			
			while (!found && count<=depth && !moves.isEmpty())
			{
				count++;
				curEdge = moves.remove();
				curPath.add(0, curEdge);
				cost+=curEdge.getCost();
				moves.init();
				if (curEdge.getSrc().getIndex()==src)
				{
					found = true;
				}
				else
				{
					for (Edge edge : curEdge.getSrc().getInNeighbors())
					{
						moves.insert(edge);
					}
				}
								
			}
			
			if (!found)
			{
				continue;
			}
			
			//search from 'v' to the dest
			moves.init();
			for (Edge edge : v.getOutNeighbors())
			{
				moves.insert(edge);
			}
			
			found = false;
			count = depth-count;
			while (!found && count<=depth && !moves.isEmpty())
			{
				count++;
				curEdge = moves.remove();
				curPath.add(curEdge);
				cost+=curEdge.getCost();
				moves.init();
				
				if (curEdge.getDst().getIndex()==dst)
				{
					found = true;
				}
				else
				{
					for (Edge edge : curEdge.getDst().getOutNeighbors())
					{
						moves.insert(edge);
					}
				}		
			}
			
			if (found)
			{
				if (cost<minCost){
					bestPath = curPath;
					minCost = cost;
				}
			}
		}
		
		long time = System.currentTimeMillis()-beginTime;
		
		if (bestPath!=null)
		{
			r.add(GraphPathResult.GRADIANT, bestPath, minCost, time);
		}
		else
		{
			r.addFailed(GraphPathResult.GRADIANT);
		}

	}

}
